Various methods are known for automatically seeking symmetrical portions of patterns. These methods are used, for the most part, in the following circumstances:
reading plans, maps, or drawings;
as a programming aid for providing a numerically controlled drilling machine with a program based on a reference artwork; and
seeking reference points for automatically controlling robots and positioning systems.
The present invention is described using the technical terms "digitizing" and "pixel".
The "digitizing" covers expressing the positions and/or values of picture elements in digital form, in particular for electronic computing purposes.
The term "pixel", i.e. picture element, covers, in conventional manner, any of the following:
a smallest or "elementary" unit of an image in digital form;
an elementary unit in the basic structure of an image-receiving sensor, for example a charge-coupled device (CCD); and
an elementary unit of a digital image as reconstituted on a screen or as stored in memory after the image has been detected by a sensor and has been processed electronically.
The problem of automatically seeking the centers of symmetrical shapes has been adequately solved in the prior art providing:
the perceptible areas of symmetrical shape are also simple in shape (e.g. circles, squares, . . . ); and
they are distinct from one another and are not combined with auxiliary patterns coming into contact therewith.
For example, French patent application No. 82 00706 (BORNELEC) describes an automatic method and apparatus for reading artwork showing printed circuit pads. The method is solely applicable to centrally symmetrical pads, and more particularly to circular pads. It is essential for there to be no other type of auxiliary pattern in the scene. The method provided proceeds by looking for successive midpoints of line segments intersecting the edges of the pads in orthogonal X and Y directions. The method starts from a point situated on the side of the pad. The horizontal extent of the pad is measured in a first direction (e.g. X) at this level. Thereafter, the perpendicularly bisecting segment through the pad is determined. The center of the pad is assumed to be the midpoint of said perpendicularly bisecting segment. This method may be implemented by using a single optoelectronic cell which is moved relative to the artwork in mutually perpendicular X and Y directions. The method is thus capable of being applied both simply and effectively. However, it is completely unusable in the common event that the artwork includes auxiliary patterns such as lines interconnecting the pads.
Also, U.S. Pat. No. 4,163,212 (W. R. BUERGER, K. K. DIXON and J. F. MONIER) describes a method and an apparatus for automatically recognizing the centers of connection pads for integrated circuits. The perceptible areas representing the pads are approximately rectangular in shape. The recommended method consists, essentially, in analyzing the scene in parallel lines along at least two perpendicular directions X and Y. For each of the directions X and Y, the curves of the centers of the segments constituted by the analysis line intersecting the rectangular perceptible area is determined. The center of the perceptible area is taken to be the intersection of said curves representative of the centers along the various analysis directions. This method works with simple patterns such as rectangles for accurately determining the centers of the perceptible areas, provided the perceptible areas are alone in the scene and are independent. If the scene includes additional auxiliary patterns, the method ceases to work.
When the perceptible areas whose centers of symmetry are to be found are attached to auxiliary patterns, the prior art provides effective solutions only for a few very special cases where the perceptible areas include identifying features.
In particular, French patent application No. 75 09 846 (G. GLIN and J. L. AMIAR) describes a method and an apparatus for providing assistance in programming a numerically controlled drilling machine on the basis of artwork representing printed circuits. This method is applicable to artwork including both pads and interconnecting lines. The method relies on giving a distinctive appearance to the perceptible areas to be identified. For example the distinctive appearance may be transparent by providing a central hole in the middle of the pads to be drilled. The image of the artwork is digitized in windows, the image is then analyzed and areas of the image possessing the distinctive appearance are identified. In particular, the central holes of the pads are recognized, as is the background region situated between the interconnecting lines (which is an error). Finally, those areas possessing the distinctive appearance and touching the edge of the image window are extracted. It is thus possible to identify solely those perceptible areas which are constituted by holes in the middles of pads. This method thus operates, a priori, perfectly well for any artwork having pads provided with central holes. However, it gives rise to errors and is thus not usable, for example with artwork having areas to be etched in the middle of ground planes, since these areas are confused with center points. In addition, the method is completely unworkable in the more general case of perceptible areas which are constituted by pads which do not include central holes.
Similarly, U.S. Pat. No. 4,295,198 (R. K. COPELAND and R. J. DIMAGGIO) describes a method and apparatus for automatically determining center holes for pads in printed circuit artwork including interconnecting lines. This method is based on a series of tests for successively verifying correspondence between various criteria of increasing selectivity. The sequencing of the these tests in order is intended to increase the speed of operation of the method. When a blank pattern is discovered, each of the tests is applied in succession. The first test, "BURST", consists in verifying whether the pattern is larger than the largest possible hole. This provides a very rough preliminary selection. The next test, "L.PATH", consists in moving along the pattern following a path constituted by line segment portions which intersect the edges at right angles, also in order to verify a maximum size condition. This test tends to eliminate lines and therefore performs a second selection. Finally, the last test, "PATH", follows a contour and thus recognizes shapes of sufficiently small size having a closed contour. The method consists in assuming that all shapes which pass all three tests are pad center holes. This method is thus solely applicable to detecting pads by means of their center holes.
There is no general method provided in the prior art for automatically seeking symmetrical perceptible areas (such as pads) in the image of a scene (such as printed circuit artwork) in which the symmetrical areas are connected to auxiliary patterns (such as interconnecting lines), and for then determining the centers of the perceptible areas after they have been found. As a result no currently-known apparatus is capable of automatically and reliably finding symmetrical perceptible areas regardless of their particular patterns, when said areas may be connected to auxiliary patterns of any shape.
All of the existing solutions:
either require special patterns, thereby considerably limiting their usefulness;
or require identifiers to be added to the patterns to be found, thereby complicating overall implementation;
or else are unusable whenever the symmetrical perceptible patterns happen to be combined with auxiliary patterns. However the present invention as claimed seeks to provide an overall solution for the above problems.